One of the important embedded devices that offer a tamper-resistant, secure environment is a smart card. The typical application execution scenario in smart cards involves the data being downloaded on it in an encrypted manner and the entire application executing inside it. This results in an important property of tamper resistance. Since no part of an application resides outside, for an attacker, smart card is like a black box inside which nobody knows what is going on. In other words, one is unable to observe application properties from outside the card offering tamper resistance.
A big concern of new generation of smart cards is memory resource limitation. Smart cards typically have only 8–64 KB memory which prevents large applications from residing on the smart card. Typically, multiple applications spread across multiple vendors require a high inter-operability and need large amount of resources. Added to the resource limitation are security related overheads which make even lesser space available to application developers. For example, complex encryption/decryption schemes, advanced security and transaction protocols and various authentication applications such as biometric codes have large data and/or code segments and it is a major struggle to put these features inside smart cards. This has led smart card application domains to be very limited and customized. In order to facilitate multi-applications and/or to fit large applications in the card, they must be broken into pieces. In other words, the smart card memory would hold only those parts of applications currently active or ready-to-execute. However, partitioning an application means that part of it will reside outside of the card. Furthermore, application partitions transmitted to the smart card could reveal the application behavior which in turn could be used by an attacker to launch a malicious attack. Thus, one must ensure that the partitions that are downloaded to the card do not reveal information.
There are many different means by which information leakage occurs as a result of program behavior. They are based on observable program properties by the attacker and include timing behavior, power behavior and control flow behavior. For example, by observing timing, one may guess that a loop is executing or by observing power consumption, or one may guess that a lot of memory operations are going on. This information can then be used to tamper with the secure system. Leakage of timing or power information is a somewhat indirect way to get information about the program properties and an attacker might have to resort to somewhat involved experiments to get the differential behavior. Leakage of control flow behavior of an application on the other hand, can be very dangerous and it is much simpler for an attacker to find out the differential behavior. Even arbitrary partitioning can introduce control flow information leakage and present a security hazard, which is the central problem encountered in program partitioning for tamper-resistant devices.
The potential danger of arbitrary partitioning is illustrated with reference to FIGS. 1A and 1B. FIG. 1A shows a basic and naïve partitioning algorithm 10, which partitions the program into basic blocks, and FIG. 1B shows a Control Flow Diagram (CFG) 11 corresponding to the algorithm 10. Briefly, this algorithm 10 allows fine control over downloading only those parts of the program which are needed during execution.
Systems such as Die-Hellman and RSA, as are known in the art, may include, for example, private key operations consisting of computing R−yx mod n, where n is public and y can be found by an eavesdropper. The attacker's goal is to find x, the secret key. To illustrate the problem, it may be presumed that the implementation uses the simple modular exponentiation algorithm of FIG. 1A which computes R=yx mod n, where x is w bits long. The corresponding CFG 11 for this small partition of code is shown in FIG. 1B.
Assuming the algorithm is used to partition a program transmitted to a smart card, where the card side will ask for a program partition every time it needs it (i.e., it does not cache any program partitions for memory efficiency purpose), it is apparent that inside the loop body if the current examined bit of x is 1, then the IF-part is executed (block 16). If the current examined bit of x is 0, then the Else-part is executed (block 18). The algorithm loop (blocks 14, 20) result in a sequence of IF or ELSE blocks being transmitted through the network. If the attacker monitors this sequence, from its knowledge the attacker can guess whether the respective bits of x were 0's or 1's and obtain the secret key x. The attacker need not know whether it is a IF part or ELSE part; mere ability to differentiate IF part and ELSE part enables the guess of key x, due to the fact that the key, or its complement, was guessed. The attack thus utilizes the different program partition sequences to infer the program behavior.
The concept behind the type of attack illustrated in FIGS. 1A and 1B is similar to timing and power differential attacks. Each method seeks to exploit information from the differences that are available to the attacker. All an attacker needs to do is to sniff mobile code packets from the network during transmission, match them to the ones previously transmitted and then try to guess the behavior from the sequence constructed. Armed with a reasonable computing power and a network tap, an attacker can exploit the security deficiencies of a system. It will also be appreciated that even if the downloaded partitions are encrypted it such an attack is not prevented. Typically, because a given partition and its encrypted version will have one to one relationship, an attacker can match encrypted versions of multiply transmitted partitions, sequence them and then exploit the same information from the encrypted sequence as she would from the unencrypted one.
In the illustrate example described above, it is clear that the major problem of partitioning by basic blocks is that the resulting partition exposes all the control flow information. After multiple iterations of a loop, by watching the sequence of program partitions transmitted, the attacker can know there is a loop and which partition is loop entry, which is loop end. The attacker can also know inside the loop body there is an IF-ELSE structure and which is the program partition controlling the branch. The attacker can virtually deduce all control information of the source program, which will lead to great potential security hole.
As is apparent from the above discussion and illustrative example, what is therefore needed are systems, methods and computer program products for partitioning a program while concealing control flow information such that an attacker can not guess a program's behavior by observing the program partitions transmitted through the network that are downloaded to a device. What is also needed is a method and computer program products for partitioning the code and data of a program to permit program partitions to run on a memory constrained device while ensuring tamper resistance during the downloading of the program partitions to the device.